package 滑动窗口技巧与相关题目;

// K个不同整数的子数组
// 给定一个正整数数组 nums和一个整数 k，返回 nums 中 「好子数组」 的数目。
// 如果 nums 的某个子数组中不同整数的个数恰好为 k
// 则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
// 例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。
// 子数组 是数组的 连续 部分。
// 测试链接 : https://leetcode.cn/problems/subarrays-with-k-different-integers/

import java.util.Arrays;

public class Code06_SubarraysWithKDifferentIntegers {

    public int subarraysWithKDistinct(int[] nums, int k) {
        return numsOfMostKinds(nums, k) - numsOfMostKinds(nums, k - 1);
    }

    public static int MAXN = 20001;

    public static int[] cnts = new int[MAXN];

    //  arr 中有多少子数组，数字种类不超过 k
    // arr的长度是n，arr里的数值在 1~n 之间
    public static int numsOfMostKinds(int[] arr, int k) {
        // 词频统计表，清空，认为现在词频都是 0
        Arrays.fill(cnts, 1, arr.length, 1);
        int ans = 0;
        for(int l = 0, r = 0, collect = 0; r < arr.length; r++){
            // r位置的字符刚进来，如果r位置的词频++之后的值为1，则说明是一种新的数
            if(++cnts[arr[r]] == 1){
                // 种类增加
                collect++;
            }
            while (collect > k){
                // l往右，（吐数字）
                // l位置字符的词频如果 --之后是0，则说明，少了一种数
                if(--cnts[arr[l++]] == 0){
                    // 词频下降
                    collect--;
                }
            }
            ans = r - l + 1;
        }
        return ans;
    }
}
